Pedersen hash
Pedersen commitments for a collision-resistant hash function
非効率性のためpaperが'91にpublishされてからハッシュ関数としては用いられなかったが、SNARKsフレンドリーなハッシュ関数としては効率的。
衝突耐性としては、discrete logのレベルになってしまう。
commitment schemes
一方が秘密にしておきたい値をcommitし、必要なパラメーターを明らかにすれば後でそのcommitした値を明らかにできるscheme。
hiding
値xに対してそのcommitmentのC(x)を関連づけることができない。
つまり、C(x)からxに関する情報は何も得られない。
binding
２つの異なる値から同じcommitmentを生成することはできない。
Pedersen Commiement Scheme
tl;dr
commitment
$ commitment = sha256(blindingFactor || data)
commitmentの加算
$ C(BF1, data1) + C(BF2, data2) == C(BF1 + BF2, data1 + data2)
$ C(BF1, data1) - C(BF1, data1) == 0
情報論理的安全性
例えば、平文の大きさがn bitsのとき2^n通り試してみないと分からない暗号は情報論理的に安全。
計算量的安全性よりも一般的に強い。
ワンタイムパッド
計算量的安全性
暗号の攻撃に必要な計算量が秘密鍵サイズnに関するcを定数として$ O(x^c)よりも大きいもの。
つまり、敵の計算能力が限られている場合の安全性
ある暗号方式を破るために非常に多くの計算量が必要であれば現実的には不可能
鍵自体の再利用が可能になり暗号化方式としては計算量的安全性をもつ暗号方式が主流。
pedersen commitment schemeは情報論理的、計算量的に安全なbindingでありnon-interactiveなccommitment scheme
$ qを大きなprimeとして$ q = 2q+1
Gをqを位数とする巡回群のgenerator、aを同じ巡回群からランダムに選び以下のHを計算。
$ H = aG
このaは秘密値
commitment
rをpを位数とする巡回群からランダムに選び、値xをcommitする。
$ C(x) = rH + xG
GとHはパブリック
rのrandomnessがhidingしてる。
decommitment
xが明らかにされC(x)を再計算し受け取ったcommitmentと一致するか検証する。
加法準同型
$ C(r_1, a_1) + C(r_2, a_2) = r_1H + a_1G + r_2H + a_2G = (r_1+r_2)H+(a_1+a_2)G = C(r_1+r_2,a_1+a_2)
つまり、a1とa2のcommitmentの合計はa1+a2のcommitmentと一致する。
From Zero (Knowledge) to Bulletproofs.
Pedersen commitment
Hinding: commitmentからはcommitした値が分からない
Binding: コミットした値を変えることはできない
C=rH+vG : H: Gとは異なるベースグループ
例えば、Gのx座標をsha256した値をHのx座標とし一方のy座標を使用する。
もしrH+aG=sH+bGとなる値が見つかる場合はH=(b-a)/(r-s)GとなりECDLPを破っていることになる。
つまりもし同じcommitmentを見つけた場合は、a=a'であることが確認できる。
issue
実装